572. The
lesson of mathematics
At
the beginning of each lesson, the math teacher Guzel Zakievna writes a positive
integer n on the board. During the lesson, the students try to find as
many prime factors of this number as possible. At the end of the lesson, the
generous Guzel Zakievna rewards all students who found the maximum number of
prime factors with a candy.
Vasya,
a student who loves sweets, asks for your help to secure a candy from Guzel
Zakievna. For the given number n, print all its prime factors and the
powers with which they occur in the number.
Input.
One positive integer n (n ≤ 109).
Output.
Print all the prime factors of the number n in
ascending order. For each factor, specify the power with which it occurs in n,
if the power is greater than one. The output format should match the example.
|
Sample input |
Sample output |
|
3240 |
2^3*3^4*5 |
SOLUTION
factorization
Algorithm analysis
The task is to
factorize the number n. To do this, iterate through all its possible
prime divisors from 2 to 
. For each divisor, count how many
times it divides n.
Algorithm implementation
The factor function performs the factorization of n into its
prime factors.
void factor(int n)
{
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i) continue;
The
number i is a divisor of n. In the variable c, compute the
power with which it appears in the factorization of n.
int c = 0;
while (n % i ==
0) n /= i, c++;
Print
the factor ic. If the
power c = 1, print only i. Otherwise, print the factor i
along with its power.
if (c > 1) printf("%d^%d",i,c);
else printf("%d",i);
If
the number n is not fully factorized
yet (n > 1), print a
multiplication sign.
if (n > 1) printf("*");
}
If,
after completing the loop, the value of n is greater than 1, it is a
prime number.
if (n > 1) printf("%d",n);
printf("\n");
}
The main part of the program. Read the input number n and start its factorization.
scanf("%d",&n);
factor(n);
Python implementation
import math
The factor function performs the
factorization of n into its prime factors.
def factor(n):
for i in range(2, math.isqrt(n) + 1):
if n % i: continue
The number i is a divisor of n. In the
variable c, compute the power with which it appears in the factorization
of n.
c = 0
while n % i == 0:
n //= i
c += 1
Print the factor ic.
If the power c = 1, print only i. Otherwise, print the factor i
along with its power.
if c > 1: print(i,"^",c, sep = "", end="")
else: print(i, end="")
If the number n
is not fully factorized yet (n > 1),
print a multiplication sign.
if n > 1: print("*", end="")
If, after completing the loop, the value of n is
greater than 1, it is a prime number.
if n > 1: print(n)
else: print()
The main part of the
program. Read the input number n and start
its factorization.
n = int(input())
factor(n)